/**
 * 哈希表 时间复杂度为O(N^2)
 * 位运算 时间复杂度为O(N)
 * 直接遍历查找 时间复杂度为O(N)
 * 高斯求和 时间复杂度为O(N)
 * 二分查找 时间复杂度为O(log N)
 */
class Solution {
    // 哈希表
    public int takeAttendance1(int[] records) {
        int n = records.length;
        int[] hash = new int[n+1];
        for (int i = 0; i < records.length; i++) {
            hash[records[i]]++;
        }
        // 值为0的就是丢失的数字
        int num = 0;
        // 这里要遍历哈希表
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] == 0) {
                num = i;
            }
        }
        return num;
    }

    // 位运算
    public int takeAttendance2(int[] records) {
        int n = records.length;
        int num = 0;
        for (int i = 0; i < n; i++) {
            num ^= (records[i] ^ i);
        }
        return num ^ n;
    }

    // 直接遍历查找
    public int takeAttendance3(int[] records) {
        // 排除特殊情况
        int n = records.length;
        if (n == 1) {
            if (records[0] == 0) {
                return 1;
            }
        }
        if (records[n-1] != n) {
            return n;
        }
        int num = 0;
        for (int i = 0; i < n; i++) {
            if (records[i] != i) {
                num = i;
                break;
            }
        }
        return num;
    }

    // 高斯求和
    public int takeAttendance4(int[] records) {
        int sum = 0;
        int i = 0;
        for (; i < records.length; i++) {
            sum += (i-records[i]);
        }
        sum += i;
        return sum;
    }

    // 二分查找
    public int takeAttendance(int[] records) {
        int left = 0;
        int right = records.length-1;
        while (left < right) {
            int mid = left + (right-left) / 2;
            if (records[mid] == mid) {
                left = mid+1;
            } else {
                right = mid;
            }
        }
        return left == records[left] ? left+1 : left;
    }
}